package Single_No_Cyclic_Linked_List;

/**
 * Created with IntelliJ IDEA.
 * Description:自己实现无头单向非循环链表的各种操作
 * User: 阿宾
 * Date: 2024-11-05
 * Time: 14:42
 */
public class MySingleList {
    //创建链表的节点
    public static class ListNode{
        public int val;//节点数据域
        public ListNode next;//指向下一个节点的引用

        //构造函数，用于初始化数据域，而node默认初始化为null
        public ListNode(int val){
            this.val = val;
        }
    }
    //设置头结点
    //头结点：即链表的第一个结点
    //此时默认值设置为null
    public ListNode head;

    /**
     * 固定方式创建一个单链表
     */
    public void createList() {
        //1.创建五个链表节点
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        //2.将节点连接起来
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        //listNode5不用设置，因为默认每个节点的next为null
        //3.将第一个结点设置为头结点
        this.head = listNode1;
    }

    /**
     * 遍历并打印链表每个节点的值
     */
    public void display() {
        //创建一个遍历结点，防止头结点位置发生改变
        ListNode cur = head;
        if(cur == null){
            System.out.println("链表为空");
            return;
        }

        while (cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();

    }

    public void display(ListNode newHead) {
        // 从指定节点开始遍历并打印每个节点的值
        //1.链表为空
        if(head == null){
            System.out.println("链表为空");
            return;
        }
        ListNode cur = newHead;
        //2.其他情况
        while (cur != null){
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    /**
     * 计算并返回链表的长度
     * @return
     */
    public int size() {
        //1.设置遍历结点，用来遍历整个链表
        ListNode cur = head;
        //2.设置计数器，用来统计结点个数
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 判断链表中是否包含指定值key
     * @param key
     * @return
     */
    public boolean contains(int key) {
        //1.设置遍历结点，用来遍历整个链表
        ListNode cur = head;
        //2.遍历链表
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        //3.跳出while循环，说明没有找到指定值key
        return false;
    }

    /**
     * 在链表头部插入一个新结点，即头插法
     * @param data
     */
    public void addFirst(int data) {
        //1.创建一个新节点,并将值写入其中
        ListNode newNode = new ListNode(data);
        //2.插入头结点位置
        newNode.next = head;
        //3.更新head指向
        head = newNode;
    }

    /**
     * 在链表尾部插入一个新节点，即尾插法
     * @param data
     */
    public void addLast(int data) {
        //1.创建一个新节点,并将值写入其中
        ListNode newNode = new ListNode(data);
        //2.链表为空时
        if(head == null){
            //新插入节点为头结点
            head = newNode;
            return;
        }
        //3.链表中有结点时
        //3.1、先遍历链表，找到链表尾结点
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        //跳出循环时，即cur.next=null,也就是cur后的节点为空，则cur当前指向的是最后一个结点
        //3.2、将新节点插入到尾结点后
        cur.next = newNode;
    }

    /**
     * 在指定位置插入一个新节点,第一个数据节点为0号下标
     * @param index
     * @param data
     */

    public void addIndex(int index, int data) {
        //1.判断下标是否合法
        if(index < 0 || index > size()){
            System.out.println("index " + index + ",不合法！");
            return;
        }
        //2.判断边界情况，即插入位置是第一个或最后一个
        if(index == 0){
            //头插法
            addFirst(data);
            return;
        }
        if(index == size()){
            //尾插法
            addLast(data);
            return;
        }
        //3.插入位置是链表其他地方
        //3.1、找到index-1的节点位置
        ListNode cur = head;
        /*while (index-1 != 0){
            cur = cur.next;
            index--;
        }*/
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        //3.2、创建新节点，将新节点指向index-1后的节点
        ListNode newNode = new ListNode(data);
        newNode.next = cur.next;
        //3.3、将index-1结点指向新节点
        cur.next = newNode;

    }

    /**
     * 删除第一次出现的指定值的节点
     * @param key
     */
    public void remove(int key) {
        //1.判断链表是否为空
        if(head == null){
            return;
        }
        //2.单独处理头结点元素
        if(head.val == key){
            head = head.next;
            return;
        }
        //3.遍历链表，找到删除节点的前一个节点,根据前一个节点删除元素
        ListNode cur = head;
        while (cur.next != null){
            if(cur.next.val == key){
                //找到删除节点，此时cur指向删除节点的前驱
                //修改cur的next为删除节点的next
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
        //4.跳出循环，说明没有找到删除节点
        System.out.println("没有找到要删除的值为"+ key + "结点");
    }

    /**
     * 删除所有指定值的节点
     * @param key
     */
    public void removeAllKey(int key) {
        //1.判断链表是否为空
        if(head == null){
            return;
        }
        /*//2.单独处理头结点元素，防止多个重复元素在链表前排，所以使用while
        //也可以不使用while,先遍历链表，然后最后使用if循环判断头结点位置元素，相当于删除头结点
        while (head.val == key){
            head = head.next;
        }
        //3.遍历链表，找到删除节点的前一个节点,根据前一个节点删除元素
        ListNode cur = head;
        while (cur.next != null){
            if(cur.next.val == key){
                //找到删除节点，此时cur指向删除节点的前驱
                //修改cur的next为删除节点的next
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }*/

        //方法2,创建一个临时节点，也就是将无头单链表变成带头的单链表
        ListNode tmp = new ListNode(-1);
        tmp.next = head;
        ListNode prev = tmp;//prev始终指向cur的前驱
        ListNode cur = head;//cur用来遍历链表
        while (cur != null){
            if(cur.val == key){
                prev.next = cur.next;
            }else {
                //prev = prev.next;
                prev = cur;
            }
            cur = cur.next;
        }
        //更新头结点
        head = tmp.next;
    }


}
